#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

DLNode* DListInit()
{
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
    if (pHead == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    pHead->next = pHead;
    pHead->prev = pHead;
    return pHead;
    //这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ，
    //最后将其进行一个初始化。最后再将 pHead 作为结果返回回去，外面就可以接收到了。
    //这就是返回值的方法，当然这里也可以采用二级指针的方法来完成。
}

DLNode* CreateNewNode(DLNodeDataType x) 
{
    DLNode* newNode = (DLNode*)malloc(sizeof(DLNode));
    if (newNode == NULL) 
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void DListPushBack(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    //DLNode* tail = pHead->prev;
    //DLNode* newNode = CreateNewNode(x);

    //tail->next = newNode;//原尾指向新尾
    //newNode->prev = tail;//新尾指回原尾
    //pHead->prev = newNode;//哨兵指到新尾
    //newNode->next = pHead;//新尾指回哨兵

    DListInsert(pHead, x);//在pHead的前一个插入就是尾插
}

void DListPrint(DLNode* pHead)
{
    //用结构体指针 pHead 接收， 这里的 pHead 表示哨兵位。
    assert(pHead != NULL);
    DLNode* cur = pHead->next;
    //遍历链表就需要从 pHead->next 开始（即第一个有效数据节点）
    //当 cur 等于 pHead 就相当于全部走了一遍了，这时就结束。
    while (cur != pHead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void DListPopBack(DLNode* pHead)
{
    assert(pHead != NULL);
    assert(pHead->next != pHead);//防止删掉哨兵位头节点
    //DLNode* tali = pHead->prev;//记录原尾等下释放
    //pHead->prev = pHead->prev->prev;//头链接到新尾
    //pHead->prev->next = pHead;//新尾链接到头
    //free(tali);

    DListEarse(pHead->prev);
}

void DListPushFront(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    //DLNode* newNode = CreateNewNode(x);
    //pHead->next->prev = newNode;//原一指回新一
    //newNode->next = pHead->next;//新一指向原一
    //pHead->next = newNode;//哨兵指向新一
    //newNode->prev = pHead;//新一指回哨兵
    ////空链表也能头插

    DListInsert(pHead->next, x);//在pHead的下一个的前面插入就是头插
}

void DListPopFront(DLNode* pHead)
{
    assert(pHead != NULL);
    assert(pHead->next != pHead);//防止删掉哨兵位头节点
    //DLNode* head = pHead->next;//记录原一等下释放
    //pHead->next = head->next;//哨兵头指向原二
    //head->prev = pHead;//原二指回哨兵头
    //free(head);
    //head = NULL;//不置空也行

    DListEarse(pHead->next);
}

DLNode* DListFind(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    DLNode* cur = pHead->next;
    //遍历链表就需要从 pHead->next 开始（即第一个有效数据节点）（和打印一样）
    //当 cur 等于 pHead 就相当于全部走了一遍了，这时就结束。
    while (cur != pHead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void DListInsert(DLNode* pos, DLNodeDataType x)//在pos之前插入
{
    assert(pos != NULL);
    DLNode* newNode = CreateNewNode(x);
    DLNode* posPrev = pos->prev;//记录pos前节点
    posPrev->next = newNode;//pos前节点指向新节点
    newNode->prev = posPrev;//新节点指回pos前节点

    newNode->next = pos;//新节点指向pos 
    pos->prev = newNode;//pos指回新节点
}

void DListEarse(DLNode* pos)
{
    assert(pos != NULL);
    assert(pos->next != pos);//防止删掉哨兵位头节点
    DLNode* posPrev = pos->prev;
    DLNode* posNext = pos->next;

    posPrev->next = posNext;//pos前节点指向pos后节点
    posNext->prev = posPrev;//pos后节点指回pos前节点
    free(pos);
    pos = NULL;//不置空也行
}

void DListDestory(DLNode* pHead)//保持接口函数的一致性就不传二级了，让使用者自己置空
{
    assert(pHead != NULL);
    DLNode* cur = pHead->next;
    while (cur != pHead)
    {
        DLNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    free(pHead);
    pHead = NULL;//不能使外面置空，让使用者自己置空
}